package com.xs.letcode;


import java.util.*;

/**
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba"也是一个有效答案。
 * <p>
 * 输入: "cbbd"
 * 输出: "bb"
 */
public class LongestHuiwen {
    public static String longestPalindrome(String s) {
        ArrayList<Character> resultList = new ArrayList();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            ArrayList<Character> list = new ArrayList();
            list.add(chars[i]);
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[i] == chars[j]) {
                    //碰到重复的字符，校验是否是回文
                    list.add(chars[j]);
                    boolean isHuiWen = true;
                    int mid = list.size() / 2;
                    int a, b ;
                    if (list.size() % 2 == 0) {
                        a = mid - 1;
                        b = mid;
                    } else {
                        a = b = mid;
                    }
                    System.out.println("--->  " + list.toString());
                    for (int x = a, y = b; x > 0; x--, y++) {
                        if (list.get(x) != list.get(y)) {
                            isHuiWen = false;
                            break;
                        }
                    }
                    if (isHuiWen) {
                        resultList = resultList.size() >= list.size() ? resultList : list;
                    } else {
                        list.clear();
                    }
                    break;
                } else {
                    list.add(chars[j]);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (Character c : resultList) {
            sb.append(c);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
//        ishuiwen();
        String s = "a2a1213a";
        System.out.println( "xs: "+ longestPalindrome(s));
        System.out.println( "pp: "+ getMaxHuiwen(s));

    }

    public static void ishuiwen() {
        ArrayList<Character> list = new ArrayList();
        list.add('b');
        list.add('1');
        list.add('1');
        list.add('b');
//        list.add('1');
//        list.add('1');

        boolean isHuiWen = true;
        int mid = list.size() / 2;
        int a, b;
        if (list.size() % 2 == 0) {
            a = mid - 1;
            b = mid;
        } else {
            a = b = mid;
        }
        System.out.println("--->  " + list.toString());
        for (int x = a, y = b; x > 0; x--, y++) {
            if (list.get(x) != list.get(y)) {
                isHuiWen = false;
                break;
            }
        }
        if (isHuiWen) {
            System.out.printf("yes");
        } else {
            System.out.printf("no");
        }
    }


    public static String getMaxHuiwen(String str) {
//        String str = "aba2b1cac1b";

        String palindrome = "";
        char[] chars = str.toCharArray();
        int length = chars.length * 2;
        for (int i = 1; i < length; i++) {
            int left = 0;
            int right = 0;
            if (i % 2 == 0) {
                left = right = i / 2;
            } else {
                left = (int) Math.ceil(i / 2.0);
                right = i / 2;
            }

            while (left > 0 && right < chars.length - 1 && chars[left - 1] == chars[right + 1]) {
                left--;
                right++;
            }

            if (right > left && right - left > palindrome.length() - 1) {
                palindrome = str.substring(left, right + 1);
            }
        }

//        System.err.println(palindrome);
        return palindrome;
    }
}
